/**
 * Reed-Solomon 纠删码编解码器
 * 用于数据恢复
 */
class RSCodec {
  constructor(dataShards, parityShards) {
    this.dataShards = dataShards;
    this.parityShards = parityShards;
    this.totalShards = dataShards + parityShards;
    
    // 初始化伽罗华域 GF(2^8)
    this.initGaloisField();
  }

  initGaloisField() {
    // 生成伽罗华域的对数表和指数表
    this.expTable = new Uint8Array(512);
    this.logTable = new Uint8Array(256);
    
    let x = 1;
    for (let i = 0; i < 255; i++) {
      this.expTable[i] = x;
      this.logTable[x] = i;
      x = this.multiply(x, 2);
    }
    
    // 扩展指数表以避免取模
    for (let i = 255; i < 512; i++) {
      this.expTable[i] = this.expTable[i - 255];
    }
    
    // 生成编码矩阵
    this.generateMatrix();
  }

  multiply(a, b) {
    // GF(2^8) 乘法，使用本原多项式 0x11d
    let result = 0;
    while (b) {
      if (b & 1) {
        result ^= a;
      }
      a <<= 1;
      if (a & 0x100) {
        a ^= 0x11d;
      }
      b >>= 1;
    }
    return result;
  }

  galoisMultiply(a, b) {
    if (a === 0 || b === 0) return 0;
    return this.expTable[this.logTable[a] + this.logTable[b]];
  }

  galoisDivide(a, b) {
    if (a === 0) return 0;
    if (b === 0) throw new Error('除数不能为 0');
    if (b === 1) return a;
    
    const logA = this.logTable[a];
    const logB = this.logTable[b];
    
    // 在 GF(2^8) 中，除法等于乘以逆元
    // log(a/b) = log(a) - log(b) mod 255
    let logResult = logA - logB;
    if (logResult < 0) {
      logResult += 255;
    }
    
    return this.expTable[logResult];
  }

  generateMatrix() {
    // 生成范德蒙德矩阵
    this.encodeMatrix = [];
    
    for (let i = 0; i < this.totalShards; i++) {
      const row = [];
      for (let j = 0; j < this.dataShards; j++) {
        if (i < this.dataShards && i === j) {
          row.push(1);
        } else if (i < this.dataShards) {
          row.push(0);
        } else {
          // 校验行使用范德蒙德矩阵
          row.push(this.power(i + 1, j));
        }
      }
      this.encodeMatrix.push(row);
    }
  }

  power(base, exp) {
    if (exp === 0) return 1;
    if (base === 0) return 0;
    
    let result = 1;
    for (let i = 0; i < exp; i++) {
      result = this.galoisMultiply(result, base);
    }
    return result;
  }

  async encode(dataShards) {
    if (dataShards.length !== this.dataShards) {
      throw new Error(`需要 ${this.dataShards} 个数据分片`);
    }

    const shardSize = dataShards[0].length;
    const allShards = [...dataShards];
    
    // 生成校验分片
    for (let i = this.dataShards; i < this.totalShards; i++) {
      const parityBuffer = Buffer.alloc(shardSize);
      
      for (let pos = 0; pos < shardSize; pos++) {
        let value = 0;
        for (let j = 0; j < this.dataShards; j++) {
          const coeff = this.encodeMatrix[i][j];
          value ^= this.galoisMultiply(coeff, dataShards[j][pos]);
        }
        parityBuffer[pos] = value;
      }
      
      allShards.push(parityBuffer);
    }
    
    return allShards;
  }

  async decode(availableShards, availableIndices) {
    if (availableShards.length < this.dataShards) {
      throw new Error(`需要至少 ${this.dataShards} 个分片进行恢复`);
    }

    const shardSize = availableShards[0].length;
    
    // 构建解码矩阵
    const subMatrix = [];
    for (let i = 0; i < this.dataShards; i++) {
      const idx = availableIndices[i];
      subMatrix.push([...this.encodeMatrix[idx]]);
    }
    
    // 求逆矩阵
    const invertedMatrix = this.invertMatrix(subMatrix);
    
    // 使用逆矩阵恢复数据
    const recoveredShards = [];
    for (let i = 0; i < this.dataShards; i++) {
      const dataBuffer = Buffer.alloc(shardSize);
      
      for (let pos = 0; pos < shardSize; pos++) {
        let value = 0;
        for (let j = 0; j < this.dataShards; j++) {
          const coeff = invertedMatrix[i][j];
          value ^= this.galoisMultiply(coeff, availableShards[j][pos]);
        }
        dataBuffer[pos] = value;
      }
      
      recoveredShards.push(dataBuffer);
    }
    
    return recoveredShards;
  }

  invertMatrix(matrix) {
    const size = matrix.length;
    
    // 创建增广矩阵 [A | I]
    const augmented = matrix.map((row, i) => {
      const identityRow = new Array(size).fill(0);
      identityRow[i] = 1;
      return [...row.map(v => v || 0), ...identityRow];
    });
    
    // 高斯-约当消元法
    for (let i = 0; i < size; i++) {
      // 寻找主元（非零元素）
      let pivot = augmented[i][i];
      let pivotRow = i;
      
      if (pivot === 0) {
        // 寻找非零主元
        for (let j = i + 1; j < size; j++) {
          if (augmented[j][i] !== 0) {
            pivotRow = j;
            pivot = augmented[j][i];
            break;
          }
        }
        
        if (pivot === 0) {
          console.error('矩阵奇异，尝试使用其他行');
          // 尝试使用任何非零元素
          for (let j = i; j < size; j++) {
            for (let k = 0; k < size; k++) {
              if (augmented[j][k] !== 0) {
                pivotRow = j;
                pivot = augmented[j][k];
                break;
              }
            }
            if (pivot !== 0) break;
          }
        }
        
        if (pivot === 0) {
          throw new Error('矩阵不可逆：无法找到非零主元');
        }
        
        // 交换行
        if (pivotRow !== i) {
          [augmented[i], augmented[pivotRow]] = [augmented[pivotRow], augmented[i]];
        }
      }
      
      // 归一化当前行（使主元为 1）
      const pivotInv = this.galoisDivide(1, pivot);
      for (let j = 0; j < size * 2; j++) {
        augmented[i][j] = this.galoisMultiply(augmented[i][j], pivotInv);
      }
      
      // 消元（使其他行的第 i 列为 0）
      for (let j = 0; j < size; j++) {
        if (i !== j) {
          const factor = augmented[j][i];
          if (factor !== 0) {
            for (let k = 0; k < size * 2; k++) {
              augmented[j][k] ^= this.galoisMultiply(factor, augmented[i][k]);
            }
          }
        }
      }
    }
    
    // 提取逆矩阵（右半部分）
    const inverse = augmented.map(row => row.slice(size));
    
    return inverse;
  }
}

module.exports = RSCodec;
